package offerbook;


/**
 *
 扩展：
 1、
 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
 f(1) = 1 ,f(2) = 2

 假设现在是第n(n>=3),那么他只有可能是从n-2层跳两步或者n-1层跳1步上来的，
 所以f(n) = f(n-1) + f(n-2)

 2、
 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法
 f(1) = 1 ,f(2) = 2
 第n个台阶，可能是从第0,第1，第2，....，第n-1个台阶跳上来的所以：
 f(n) = f(1)+ ... + f(n-1) + 1.  1代表直接跳上来
 又
 f(n-1) = f(1)+ ... + f(n-2)+ 1. 1代表直接跳上来
 所以
 f(n) = 2*f(n-1) = 2^2 * f(n-2) =...= 2^(n-1)*f(1) = 2^(n-1)

 3、
 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上m级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 先列多项式：
 f(n) =  f(n-1) + f(n-2) + f(n-3) + ... + f(n-m)
 f(n-1) = f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)
 化简得：f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-m) =
 f(n-2) + f(n-3) + ... + f(n-m)    +    f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)
  = 2* f(n-1) - f(n-m-1)

 */

public class Code09_FrogJumpStep {


    public static int frogJump1(int n) {
        if (n <= 1) {
            return 1;
        }
        return 2 * frogJump1(n - 1);
    }



    public static int frogJump2(int n, int m) {
        //当n大于m的时候是上面的公式
        if (n > m) {
            /**
             * 这里存在两项问题，又会重复计算。
             */
            return 2 * frogJump2(n - 1, m) - 2 * frogJump2(n - m - 1, m);
        }
        //当n小于等于m的时候,就和青蛙只会从1,2,...n跳相同了，不可能出现比n跳大的，此时m没有用了。frogJump1
        if (n <= 1) {
            return 1;
        } else {
            return 2 * frogJump2(n - 1, m);
        }
    }

}
